#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int Status;

typedef int QElemType;

typedef struct QNode
{
  QElemType data;
  struct QNode *next;
} QNode, *QNodePtr;

typedef struct
{
  QNodePtr front;
  QNodePtr rear;
} LinkQueue;

/**
 * @brief 初始化链队列
 * @param Q 指向链队列的指针
 * @return 状态码
 */
Status IniteQueue(LinkQueue *Q)
{
  Q->front = Q->rear = (QNodePtr)malloc(sizeof(QNode));
  if (!Q->front)
    return OVERFLOW;
  Q->front->next = NULL;
  return OK;
}

/**
 * @brief 入队操作
 * @param Q 指向链队列的指针
 * @param e 要入队的元素
 * @return 状态码
 */
Status EnQueue(LinkQueue *Q, QElemType e)
{
  QNodePtr newNode = (QNodePtr)malloc(sizeof(QNode));
  if (!newNode)
    return OVERFLOW;
  newNode->data = e;
  newNode->next = NULL;
  Q->rear->next = newNode;
  Q->rear = newNode;
  return OK;
}

/**
 * @brief 出队操作
 * @param Q 指向链队列的指针
 * @param e 指向存储出队元素的指针
 * @return 状态码
 */
Status DeQueue(LinkQueue *Q, QElemType *e)
{
  if (Q->front == Q->rear)
  {
    printf("Queue is empty!\n");
    return ERROR;
  }
  QNodePtr p = Q->front->next;
  *e = p->data;
  Q->front->next = p->next;
  if (Q->rear == p)
    Q->rear = Q->front;
  free(p);
  return OK;
}

/**
 * @brief 获取队头元素
 * @param Q 指向链队列的指针
 * @param e 存放队头元素的指针
 */
void GetHead(LinkQueue *Q, QElemType *e)
{
  if (Q->front == Q->rear)
  {
    printf("Queue is empty!\n");
    return;
  }
  *e = Q->front->next->data;
}

/**
 * @brief 判断队列是否为空
 * @param Q 指向链队列的指针
 * @return 1 表示空，0 表示非空
 */
int isEmpty(LinkQueue *Q)
{
  return Q->front == Q->rear;
}

/**
 * @brief 获取队列长度
 * @param Q 指向链队列的指针
 * @return 队列长度
 */
int QueueLength(LinkQueue *Q)
{
  int length = 0;
  QNodePtr p = Q->front->next;
  while (p)
  {
    length++;
    p = p->next;
  }
  return length;
}

/**
 * @brief 销毁链队列
 * @param Q 指向链队列的指针
 * @return 状态码
 */
Status DestroyQueue(LinkQueue *Q)
{
  QNodePtr p = Q->front;
  while (p)
  {
    Q->front = Q->front->next;
    free(p);
    p = Q->front;
  }
  return OK;
}

/**
 * @brief 打印链队列
 * @param Q 指向链队列的指针
 */
void PrintQueue(LinkQueue *Q)
{
  // if (Q == NULL || Q->front == Q->rear)
  // {
  //   printf("Queue is empty\n");
  //   return;
  // }
  QNodePtr p = Q->front->next;
  printf("Queue elements: ");
  while (p)
  {
    printf("%d ", p->data);
    p = p->next;
  }
  printf("\n");
}

int main()
{
  LinkQueue q;
  int status = IniteQueue(&q);
  if (status == OK)
  {
    // Queue initialized successfully
    printf("Queue initialized successfully\n");
  }
  // 测试入队
  EnQueue(&q, 1);
  EnQueue(&q, 2);
  EnQueue(&q, 3);
  PrintQueue(&q);
  int e;
  // 测试出队
  DeQueue(&q, &e);
  printf("Dequeued element: %d\n", e);
  // 测试获取队头元素
  GetHead(&q, &e);
  printf("Queue head: %d\n", e);
  // PrintQueue(&q);
  // while (DeQueue(&q, &e) == OK)
  // {
  //   printf("Dequeued element: %d\n", e);
  // }
  // 测试获取队列长度
  int length = QueueLength(&q);
  printf("Queue length: %d\n", length);

  // 判断队列是否为空
  if (isEmpty(&q))
  {
    printf("Queue is empty\n");
  }
  else
  {
    printf("Queue is not empty\n");
  }
  // 清空队列
  while (q.front != q.rear)
  {
    DeQueue(&q, &e);
    printf("Dequeued element: %d\n", e);
  }
  // 判断队列是否为空
  if (isEmpty(&q))
  {
    printf("Queue is empty\n");
  }
  else
  {
    printf("Queue is not empty\n");
  }
  // 销毁队列
  DestroyQueue(&q);
  return 0;
}